package newShiyan4;

import java.util.Scanner;

/**
 * 二叉排序树主类
 * 提供菜单系统，测试二叉排序树的各种功能
 */
public class BSTMain {
    private static BinarySearchTree bst = new BinarySearchTree();
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        System.out.println("========================================");
        System.out.println("    二叉排序树操作演示系统");
        System.out.println("    学号：202411671429");
        System.out.println("    姓名：易信志");
        System.out.println("========================================");

        // 初始化一些测试数据
        initializeTestData();

        int choice;
        do {
            showMenu();
            System.out.print("请选择操作（0-9）：");
            choice = scanner.nextInt();
            handleChoice(choice);
        } while (choice != 0);

        System.out.println("感谢使用！");
        scanner.close();
    }

    /**
     * 显示主菜单
     */
    private static void showMenu() {
        System.out.println("\n========== 主菜单 ==========");
        System.out.println("1. 创建二叉排序树（输入整数序列）");
        System.out.println("2. 查找元素");
        System.out.println("3. 插入元素");
        System.out.println("4. 删除元素");
        System.out.println("5. 前序遍历（递归）");
        System.out.println("6. 前序遍历（非递归）");
        System.out.println("7. 中序遍历（递归）");
        System.out.println("8. 中序遍历（非递归）");
        System.out.println("9. 后序遍历（递归）");
        System.out.println("10. 后序遍历（非递归）");
        System.out.println("11. 层序遍历");
        System.out.println("12. 显示树信息（高度、结点数）");
        System.out.println("0. 退出");
        System.out.println("===========================");
    }

    /**
     * 处理用户选择
     * 
     * @param choice 用户选择的操作编号
     */
    private static void handleChoice(int choice) {
        switch (choice) {
            case 1:
                createBST();
                break;
            case 2:
                searchElement();
                break;
            case 3:
                insertElement();
                break;
            case 4:
                deleteElement();
                break;
            case 5:
                bst.preOrderRecursive();
                break;
            case 6:
                bst.preOrderIterative();
                break;
            case 7:
                bst.inOrderRecursive();
                break;
            case 8:
                bst.inOrderIterative();
                break;
            case 9:
                bst.postOrderRecursive();
                break;
            case 10:
                bst.postOrderIterative();
                break;
            case 11:
                bst.levelOrder();
                break;
            case 12:
                showTreeInfo();
                break;
            case 0:
                break;
            default:
                System.out.println("无效的选择，请重新输入！");
        }
    }

    /**
     * 创建二叉排序树
     */
    private static void createBST() {
        System.out.print("请输入整数序列（用空格分隔，例如：50 30 70 20 40 60 80）：");
        scanner.nextLine(); // 清除缓冲区
        String input = scanner.nextLine();
        String[] numbers = input.trim().split("\\s+");

        bst = new BinarySearchTree(); // 重新创建树
        for (String num : numbers) {
            try {
                int value = Integer.parseInt(num);
                bst.insert(value);
            } catch (NumberFormatException e) {
                System.out.println("警告：'" + num + "' 不是有效整数，已跳过");
            }
        }
        System.out.println("二叉排序树创建成功！");
        System.out.print("中序遍历结果：");
        bst.inOrderRecursive();
    }

    /**
     * 查找元素
     */
    private static void searchElement() {
        System.out.print("请输入要查找的整数：");
        int data = scanner.nextInt();
        if (bst.search(data)) {
            System.out.println("元素 " + data + " 在树中找到！");
        } else {
            System.out.println("元素 " + data + " 不在树中！");
        }
    }

    /**
     * 插入元素
     */
    private static void insertElement() {
        System.out.print("请输入要插入的整数：");
        int data = scanner.nextInt();
        if (bst.search(data)) {
            System.out.println("元素 " + data + " 已存在于树中，无法重复插入！");
        } else {
            bst.insert(data);
            System.out.println("元素 " + data + " 插入成功！");
            System.out.print("中序遍历结果：");
            bst.inOrderRecursive();
        }
    }

    /**
     * 删除元素
     */
    private static void deleteElement() {
        System.out.print("请输入要删除的整数：");
        int data = scanner.nextInt();
        if (bst.delete(data)) {
            System.out.println("元素 " + data + " 删除成功！");
            System.out.print("中序遍历结果：");
            bst.inOrderRecursive();
        } else {
            System.out.println("元素 " + data + " 不在树中，无法删除！");
        }
    }

    /**
     * 显示树信息
     */
    private static void showTreeInfo() {
        if (bst.isEmpty()) {
            System.out.println("树为空！");
            return;
        }
        System.out.println("树的高度：" + bst.getHeight());
        System.out.println("树的结点数：" + bst.getNodeCount());
        System.out.print("中序遍历结果：");
        bst.inOrderRecursive();
    }

    /**
     * 初始化测试数据
     */
    private static void initializeTestData() {
        System.out.println("\n正在初始化测试数据...");
        int[] testData = { 50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85 };
        for (int data : testData) {
            bst.insert(data);
        }
        System.out.println("测试数据初始化完成！");
        System.out.print("中序遍历结果：");
        bst.inOrderRecursive();
    }
}
